package leetcode.code0792;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	class Node extends HashMap<Character, Node> {
		int end;
	}

	public int numMatchingSubseq(String s, String[] words) {
		Node root = new Node();
		for (String word : words) {
			Node cur = root;
			for (char c : word.toCharArray()) {
				cur = cur.computeIfAbsent(c, key -> new Node());
			}
			cur.end++;
		}
		char[] cs = s.toCharArray();
		int len = cs.length;
		int[][] hash = new int[len][26];
		int[] chars = new int[26];
		Arrays.fill(chars, -1);
		for (int i = len - 1; i >= 0; i--) {
			chars[cs[i] - 'a'] = i;
			hash[i] = Arrays.copyOf(chars, 26);
		}
		return f(root, 0, hash);
	}

	private int f(Node root, int index, int[][] hash) {
		if (index == hash.length) {
			return 0;
		}
		int ans = 0;
		for (Map.Entry<Character, Node> entry : root.entrySet()) {
			char key = entry.getKey();
			Node node = entry.getValue();
			int end = node.end;
			if (hash[index][key - 'a'] != -1) {
				ans += end;
				ans += f(node, hash[index][key - 'a'] + 1, hash);
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(1, this.numMatchingSubseq("dcaog", H.str2array2("[\"cop\",\"dog\",\"cat\"]")));
		H.compare(3, this.numMatchingSubseq("abcde", H.str2array2("[\"a\",\"bb\",\"acd\",\"ace\"]")));
		H.compare(2, this.numMatchingSubseq("dsahjpjauf",
				H.str2array2("[\"ahjpjau\",\"ja\",\"ahbwzgqnuk\",\"tnmlanowax\"]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
